Diverse forms of personal computers, such as desktop computers for office and laptop computers for a mobile environment have been developed for commercial and personal use. A computer system may include a main memory and an external storage device. The external storage device may have a large memory capacity and a low unit price. External storage devices include a conventional hard disk drive (HDD) and a floppy disk drive (FDD) used in a disk storing medium. Generally, disk storage provides a large memory capacity at a low price, but may require delicate mechanical techniques to perform various operations, (e.g., disk searching), with a magnetic head. Thus, the disk storage may be damaged by physical impact, which makes it less reliable than other kinds of memory devices. External semiconductor memory devices adopting a flash memory, such as flash Electrically Erasable Programmable Read-Only Memory (EEPROM), provide an executable alternative to disk storage in an arbitrary environment. Flash memory devices are non-volatile memory devices that are programmable more than once. Moreover, flash memory devices have relatively simple structures that can be realized at low cost. Because a flash memory device may consume a low level of power and is compact, light, and less fragile to physical impact, the flash memory devices are frequently suitable for a mobile environment. One drawback to using a flash memory device includes the requirement that an erasure operation should be performed before a program operation. Another drawback includes the requirement of using high voltages (e.g., 12V or 20V) to perform erasure operations.
A host processor may access an external storage device by generating a logical address. The logical address refers to an arbitrary location in a logical memory space recognized by host software, (i.e., an operating system or an application). A logical address is transformed into a physical address corresponding to a physical memory space of an external storage device. Generally, an external storage device using flash memory requires additional software called disk emulation software to secure compatibility with the host during an access operation. The compatibility between the host and the external flash storage device can be achieved by operating a conventional file system such as a flash translation layer (FTL). In this case, the host processor recognizes the external flash storage device as an HDD/SDRAM and accesses the external flash memory device in the same manner as it accesses an HDD/SDRAM. The FTL connects a flash memory card to a file system used in a particular operating system and it does not allow writing more than once to the same address without prior erasure.
The FTL functions include management of logical address-physical address mapping, management of bad blocks, management of data preservation against unexpected power cutoff, and management of abrasion. The core function among the FTL functions involves address mapping. Exemplary address mapping schemes are presented in U.S. Pat. No. 5,404,485 entitled “Flash file system”; U.S. Pat. No. 5,937,425 entitled “Flash file system optimized for page-mode flash technologies”; and U.S. Pat. No. 6,381,176 entitled “Method of driving remapping in flash memory and flash memory architecture suitable therefore,” the disclosures of which are hereby incorporated herein by reference.
In the case where a flash memory is accessed on a block basis, the flash memory is divided into a plurality of blocks. A number called a physical block number is allocated to each of the blocks sequentially, and a virtual number for a block a user thinks is being used in called a logical block number. A method for mapping the logical block number to a physical block number includes (ii) a block mapping scheme, (iii) a sector (or page) mapping scheme, and (iii) a log mapping scheme. In an FTL using a mapping scheme, data having logically consecutive addresses can be registered in physically different locations. Since a flash memory has a larger erasion unit than a writing unit or a program unit, when writing into different physical locations reaches a predetermined level, it is necessary to collect consecutive data dispersed in physically different locations into the same address space by using a free block. This operation is called merging.
Merging operations using the aforementioned block mapping scheme, sector mapping scheme, and log mapping scheme will now be described in detail. Prior to the description on the merging operations, it is assumed herein that a flash memory is divided into a plurality of memory blocks and each memory block is formed of a plurality of pages or sectors. A reference ‘PBN’ stands for a physical block number and a reference ‘PPN’ denotes a physical page number, while a reference ‘LPN’ stands for a logical page number.
Block Mapping Scheme
Merging operation using a block mapping scheme will be described herein with reference to FIG. 1. According to the block mapping scheme, when data is stored in an arbitrary memory block, it is stored consecutively in the pages of the memory block. For example, when data is updated or re-registered in the ith page (i.e., PPNi), of a memory block having a physical block number of ‘2,’ (i.e., PBN2), data stored in the other pages except the ith page PPNi, for which the update is requested, are copied into corresponding pages of an empty block, which is called a free memory block (e.g., PBN3). Then, the data to be stored in the page PPNi of the memory block PBN2 is updated/re-registered into the corresponding ith page of the memory block PBN3. Subsequently, the entire memory block PBN2 is erased and becomes a free memory block. In the block mapping scheme, a merging operation should be carried out whenever new data is updated into a page containing old data. Block mapping of data between a physical block number and a logical block number is typically managed using a block mapping table.
Sector (Page) Mapping Scheme
A merging operation using a sector mapping scheme will be described herein with reference to FIGS. 2A and 2B. According to the page (or sector) mapping scheme, data is written into pages of a memory block sequentially. Herein, a page has the same size as a sector, but it is obvious to those of ordinary skill in the art that one page can be formed of a plurality of sectors. For example, data in a logical page LPN0 is stored in a physical page PPN0, and data in a logical page LPN1 is stored in a physical page PPN1. Data in a logical page LPN2 is stored in a physical page PPN2. When first data is to be updated into a logical page LPN1, this first data is stored in a physical page PPN3 and the physical page PPN1 is updated so that it stores null data, which is marked as ‘X’ in FIG. 2A. In addition, when data is to be updated into a logical page LPN0, the second data is stored in a physical page PPN4 and the physical page PPN0 is updated so that it stores null data, which is marked as ‘X’ in FIG. 2A. If writing is carried out with respect to all pages, that is, if there is no free page in the memory block PBN0, the merging operation is performed when the writing into the memory block PBN0 is requested. As shown in FIG. 2A, only valid data of the memory block PBN0 (i.e., physical pages PPN2 to PPN5), is copied into corresponding pages PPN10 to PPN13 of a free memory block PBN1. Then, the data of a logical page LPN0 in the memory block PPBN1, for which the writing operation is requested, is stored in a physical page PPN14 of the free memory block PBN1. The physical page PPN0 of the memory block PBN1 will then be processed so that it stores null data, which is marked as ‘X’ in FIG. 2A. Subsequently, the physical memory block PBN10 will be erased. A mapping table is modified as shown in FIG. 2B and the modified mapping table is managed by a flash translation layer (FTL).
Log Mapping Scheme
Merging operation using a log mapping scheme will be described herein in detail with reference to FIGS. 3A to 3C. According to the log mapping scheme, as shown in FIG. 3A, memory blocks are divided into a data region, a log region, and a meta region, and a table of the mapping data is managed by an FTL. In the log mapping scheme, some memory blocks of the data region are designated as the memory blocks of a log region. For example, it is assumed that a flash memory includes 9 memory blocks PBN0 to PNB8. When the memory blocks are not yet used, memory blocks PBN0 to PBN4 are defined as the data region, and memory blocks PBN5 to PBN7, are defined as the log region, and a memory block PBN8 is defined as the meta region, individually. Herein, the memory blocks PBN0 and PBN2 of the data region are designated as the memory blocks PBN5 and PBN6 of the log region, and a memory block PBN7 of the log region is designated as a free memory block. Mapping data between memory blocks, mapping data between the memory region and the log region, and mapping data of the log region are managed in a block mapping table, a log block mapping table, and a log mapping table, respectively. Each memory block is formed of a plurality of pages or a plurality of sectors.
When data is to be written into a memory block PBN0, the data is not written into the memory block PBN0 directly but is stored in a memory block PBN5 of the log region, which corresponds to the memory block PBN0. For example, when data corresponding to a logical page LPN2 is to be written into a memory block PBN0, the data is written into a physical page PBN0 of the memory block PBN5 of the log region. Likewise, when data corresponding to a logical page LPN0 is to be written into the memory block PBN0, the data is written into a physical page PBN1 of the memory block PBN5 of the log region. When data is to be written into the memory block PBN1, merging is carried out as follows because a memory block of the log region corresponding to the memory block PBN1 is designated. First, it is determined whether there is a free memory block in the log region or the data region. If there is a free memory block in the log region, as illustrated in FIG. 3B, valid data stored in any one memory block, for example, a memory block PBN5 among the memory blocks PBN5 and PBN6 of the log region, is copied into a free memory block PBN7. Then, valid data stored in the memory block PBN0 of the data region, which corresponds to the memory block PBN5, is copied/transferred into the memory block PBN7. The copying process is shown in FIG. 3B. After the memory blocks PBN0 and PBN5 are erased, as shown in FIG. 3C, the memory block PBN5 of the log region is designated as the free memory block, and the memory block PBN0 of the data region is designated as a memory block of the log region, while the memory block PBN7 is designated to a memory block of the data region. Finally, the data to be written into the memory block PBN1 is written into the memory block PBN0 of the log region. The mapping data of the block mapping table, the log block mapping table, and the log mapping table are managed by an FTL and they are stored in the meta region PBN8.
Because the page mapping scheme manages the mapping data on a page basis, there is a shortcoming because it typically requires a large mapping table while there is an advantage because it can write small quantities of data easily. The log mapping scheme has a disadvantage in that the merging should be carried out whenever a small quantity of data is written into different data blocks, while it has an advantage in that it can write a large quantity of data easily. Also, the log mapping scheme has an advantage in that it has a relatively small mapping table compared to the page mapping scheme.
Generally, a flash memory system having a flash memory as a storage medium manages the flash memory using a single FTL. Flash memories have diverse access patterns: a pattern where part of contents stored in a memory block are updated and a pattern where free memory blocks are all used for new contents. However, since different access patterns are processed by only a single FTL, the performance of the entire system can be degraded.